#!/usr/bin/env python
# -*- coding: UTF-8 -*-
"""
@Project: DataStructure-Python 
@File: Shell-Sort.py
@Author: Dragon Geek
@Date: 2021/4/19 17:46
@Description: 
"""


def shell_sort(list_unsorted):
    """
    @param list_unsorted: the list that is unsorted in bubble sort algorithm
    @return: the list that has be sorted in bubble sort algorithm
    """
    n = len(list_unsorted)
    for i in range(1, n):
        # for j in range(i, 0, -1):
        #     if list_unsorted[j] < list_unsorted[j - 1]:
        #         list_unsorted[j], list_unsorted[j - 1] = list_unsorted[j - 1], list_unsorted[j]
        #     else:
        #         break
        j = i
        while j > 0:
            if list_unsorted[j] < list_unsorted[j - 1]:
                list_unsorted[j], list_unsorted[j - 1] = list_unsorted[j - 1], list_unsorted[j]
                i -= 1
            else:
                break
